﻿#pragma once
#include "Index.h"
class IMaxestSumOfRingSubArr
{
public:
	/**
	 * 环形数组的连续子数组最大和.
	 * https://www.nowcoder.com/practice/53a9f1ba687440cc9c641c2b042a59d7?tpId=230&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230
	 *
	 * 给定一个长度为 nn 的环形整数数组，请你求出该数组的 非空 连续子数组 的最大可能和 。
	 * 环形数组 意味着数组的末端将会与开头相连呈环状。
	 * 例如，对于数组 [1,3,-5,2,-4][1,3,−5,2,−4]而言，第一个数 1的前一个数是最后一个数 -4
	 */
	virtual int getMaxSumOfRingSubArr(std::vector<int>& arr) = 0;
};

class MaxestSumOfRingSubArr
{
public:
	class DP:public IMaxestSumOfRingSubArr
	{
	public:
		/**
		 * 滑动窗口的思想 和 常规的连续子数组的最大和DP转移方程 dp[i]=max{dp[i-1]+a[i],a[i]}
		 * 时间:O(n^2) 空间:O(1)
		 */
		int getMaxSumOfRingSubArr(std::vector<int>& arr) override
		{
			if (arr.empty())
				return 0;
			const int arrSize = arr.size();

			int resultMaxSum = arr[0];
			//当前子数组的和
			int subArrSum = arr[0];
			//子数组开始的位置
			int subArrStart = 0;

			for (int i = 1; i < 2 * arrSize; ++i)
			{
				//num可以在之前子数组size不溢出的情况下归入前一个子数组
				if (subArrSum > 0)
				{
					const int subArrSize = i - subArrStart + 1;
					//归入后子数组size会溢出，则将开始位置右移
					if (subArrSize > arrSize)
					{
						//至少先右移一位
						subArrSum -= arr[subArrStart % arrSize];
						subArrStart++;

						//后面的右移要保证剩余的固定右边界子数组和要最大
						int maxSum = 0;
						int curSum = 0;
						int newStart = i;
						for (int k = newStart - 1; k >= subArrStart; --k)
						{
							curSum += arr[k % arrSize];
							if (curSum > maxSum)
							{
								maxSum = curSum;
								newStart = k;
							}
						}

						//更新开始位置右移后的子数组信息
						subArrStart = newStart;
						subArrSum = maxSum;
					}
				}

				const int& num = arr[i % arrSize];
				//归入前一个子数组,此时保证归入的子数组不会size溢出
				if (subArrSum > 0)
				{
					subArrSum += num;
				}
				//不归入前一个子数组
				else
				{
					subArrSum = num;
					subArrStart = i;
				}
				//收集结果
				resultMaxSum = std::max<>(subArrSum, resultMaxSum);
			}
			return resultMaxSum;
		}
	};

	class MaxAndMin:public IMaxestSumOfRingSubArr
	{
	public:
		/**
		 * 求最大和可以反过来先求最小和，最大和跟最小和的数组必定首尾相连，中间不可能有空位，
		 * 分成两个数组，如果最小和是从尾部跳到首部，那最大和就在数组中间，就是正常的dpmax，
		 * 如果最大和是从尾部跳到首部，那最小和就在数组中间，就是正常的dpmin，sum-dpmin就是最大和；
		 * 特殊情况，如果dpmin=sum就代表全是负数，也是正常的dpmax；
		 *
		 * 时间:O(n) 空间:O(1)
		 */
		int getMaxSumOfRingSubArr(std::vector<int>& arr) override
		{
			if (arr.empty())
				return 0;
			const int arrSize = arr.size();

			int sum = arr[0];
			int dpMax = arr[0], dpMin = arr[0];

			int max = arr[0], min = arr[0];

			for (int i = 1; i < arrSize; ++i)
			{
				max = std::max<>(max + arr[i], arr[i]);
				min = std::min<>(min + arr[i], arr[i]);

				dpMax = std::max<>(max, dpMax);
				dpMin = std::min<>(min, dpMin);

				sum += arr[i];
			}

			if (dpMax < 0)
				return dpMax;
			return std::max<>(dpMax, sum - dpMin);
		}
	};
};

